package com.example.hashtable20.hashtable;

import java.util.HashMap;

/**
 * @description 基于散列表的最少使用策略 LRU（Least Recently Used）
 * @auther lijiewei
 * @date 2021/9/14 10:00
 */
public class LRUBaseHashTable<K, V> {

    /** 默认链表容量. */
    private final static Integer DEFAULT_CAPACITY = 10;

    /** 头结点（哨兵）. */
    private DNode<K, V> headNode;

    /** 尾节点（哨兵）. */
    private DNode<K, V> tailNode;

    /** 链表长度. */
    private Integer length;

    /** 链表容量. */
    private Integer capacity;

    /** 散列表存储key. */
    private HashMap<K, DNode<K, V>> table;

    public LRUBaseHashTable(int capacity) {
        this.capacity = capacity;
        this.length = 0;

        headNode = new DNode<>();
        tailNode = new DNode<>();

        headNode.setNext(tailNode);
        tailNode.setPrev(headNode);

        table = new HashMap<>();
    }

    public LRUBaseHashTable() {
        this(DEFAULT_CAPACITY);
    }

    /**
     * 新增
     * @param key 键
     * @param value 数据
     * @return
     * @author lijiewei
     * @date   2021/9/14 11:25
     */
    public void add(K key, V value) {
        DNode<K, V> node = table.get(key);
        if (node == null) {
            //不存在，链头新插入
            DNode<K, V> newNode = new DNode(key, value);
            table.put(key, newNode);
            addNode(newNode);

            if (++length > capacity) {
                DNode<K, V> tail = popTail();
                table.remove(tail.getKey());
                length--;
            }
        } else {
            //已经存在，更新值，删除后，链头新插入
            node.setValue(value);
            moveToHead(node);
        }
    }

    /**
     * 获取节点数据
     * @param key 键
     * @return
     * @author lijiewei
     * @date   2021/9/14 13:42
     */
    public V get(K key) {
        DNode<K, V> node = table.get(key);
        if (node == null) {
            return null;
        }
        moveToHead(node);
        return node.getValue();
    }

    /**
     * 移除节点数据
     * @param key 键
     * @return
     * @author lijiewei
     * @date   2021/9/14 13:45
     */
    public void remove(K key) {
        DNode<K, V> node = table.get(key);
        if (node == null) {
            return;
        }
        removeNode(node);
        length--;
        table.remove(key);
    }

    /**
     * 打印所有节点
     * @return
     * @author lijiewei
     * @date   2021/9/14 13:50
     */
    public void printAll() {
        DNode<K, V> node = headNode.getNext();
        while(node.getNext() != null) {
            System.out.print(node.getValue()+", ");
            node = node.getNext();
        }
        System.out.println();
    }


    /**
     * 将新节点加到头部
     * @param newNode 新节点
     * @return
     * @author lijiewei
     * @date   2021/9/14 11:36
     */
    private void addNode(DNode<K,V> newNode) {
        newNode.setNext(headNode.getNext());
        newNode.setPrev(headNode);

        headNode.getNext().setPrev(newNode);
        headNode.setNext(newNode);
    }

    /**
     * 弹出尾部数据节点
     * @return
     * @author lijiewei
     * @date   2021/9/14 13:33
     */
    private DNode<K, V> popTail() {
        DNode<K, V> node = tailNode.getPrev();
        removeNode(node);
        return node;
    }

    /**
     * 移除节点
     * @param node 要移除的节点
     * @return
     * @author lijiewei
     * @date   2021/9/14 13:36
     */
    private void removeNode(DNode<K,V> node) {
        node.getPrev().setNext(node.getNext());
        node.getNext().setPrev(node.getPrev());
    }

    /**
     * 将节点移到头部
     * @param node 节点
     * @return
     * @author lijiewei
     * @date   2021/9/14 13:40
     */
    private void moveToHead(DNode<K,V> node) {
        removeNode(node);
        addNode(node);
    }



}
